0%

Self-Learned Algorithms - 05

Posted on Edited on In

Self-Learned Algorithms - 05

This is my learning note about algorithms.

Reference

104.最大深度与DFS

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

题解

  • 深度优先搜索，用递归或者用栈都可以。

解法

  • 递归
1
return 0 if not root else max(self.maxDepth(root.left)+1,self.maxDepth(root.right)+1)
  • BFS
1
2
3
4
5
6
7
8
9
10
11
# BFS
if root is None:
	return 0
queue = [(1, root)]
while queue:
  depth, node = queue.pop(0)
  if node.left:
  	queue.append((depth+1,node.left))
  if node.right:
  	queue.append((depth+1,node.right))
return depth
  • DFS：DFS最后得到的深度不一定是最大深度，所以要用max判断；遍历时节点右孩子先入栈，左孩子再入栈（左右的先后是否有区别呢）
1
2
3
4
5
6
7
8
9
10
11
12
13
# DFS
if root is None:
	return 0
stack = [(1, root)]
depth = 0
while stack:
  cur_dep, node = stack.pop()
  depth = max(depth, cur_dep)
  if node.right:
  	stack.append((cur_dep+1,node.right))
  if node.left:
  	stack.append((cur_dep+1,node.left))
return depth

[很不错的一篇有关递归的讲解][https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/python-3di-gui-zi-ding-xiang-xia-zi-di-xiang-shang/]

102.层次遍历与BFS

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

题解

解法

  • BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
queue = collections.deque()
queue.append(root)
res = []
while queue:
  size = len(queue)
  level = []
  for _ in range(size):
    cur = queue.popleft()
    if not cur:
    	continue
    level.append(cur.val)
    queue.append(cur.left)
    queue.append(cur.right)
  if level:
  	res.append(level)
return res
  • DFS： DFS 不是按照层次遍历的。为了让递归的过程中同一层的节点放到同一个列表中，在递归时要记录每个节点的深度 level。递归到新节点要把该节点放入 level 对应列表的末尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def levelOrder(self, root):
  """
  :type root: TreeNode
  :rtype: List[List[int]]
  """
  res = []
  self.level(root, 0, res)
  return res

def level(self, root, level, res):
  if not root: return
  if len(res) == level: res.append([])
  res[level].append(root.val)
  if root.left: self.level(root.left, level + 1, res)
  if root.right: self.level(root.right, level + 1, res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
### 注意区别，节点对象list1(代码中的nodes) 和 节点值list2(代码中的values)
# pseduo code
# 节点对象list1初始仅包含根节点，后续仅保存一层节点
# 节点值list2初始为空，后续累积保存整棵树的所有节点值
# while 节点对象list1不为空:
#     收集当前层节点对象list1的每一个值，添加保存至节点值list2
#     收集当前层节点对象list1的每一个子节点，覆盖保存至节点对象list1
# 返回收集完全的节点值list2

nodes = [(root,)]
values = []
while nodes:
  values.append([r.val for n in nodes for r in n if r])
  nodes = [(r.left, r.right) for n in nodes for r in n if r]
return values[:-1]

98.验证二叉搜索树

https://leetcode-cn.com/problems/validate-binary-search-tree/

题解

  • 二叉搜索树 (Binary Search Tree)，(又：二叉查找树，二叉排序树)它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

解法

  • 递归+最大值最小值
1
2
3
4
5
6
7
8
def dfs(node, min_val, max_val):
  if not node:
  	return True
  if not min_val < node.val < max_val:
  	return False
  return dfs(node.left, min_val, node.val) and dfs(node.right, node.val, max_val)

return dfs(root, float('-inf'), float('inf'))
1
2
3
4
5
6
7
8
9
10
11
12
13
stack = []
p = root
pre = None
while p or stack:
  while p:
    stack.append(p)
    p = p.left
  p = stack.pop()
  if pre and p.val <= pre.val:
  	return False
  pre = p
  p = p.right
return True

700.二叉搜索树中的搜索

https://leetcode-cn.com/problems/search-in-a-binary-search-tree/

题解

  • 既然是一个二叉搜索树那么问题就很简单了

解法

  • 递归
1
2
3
4
5
6
7
8
9
10
if not root:
	pass
else:
  if root.val == val:
  	return root
  elif root.val >val:
  	return self.searchBST(root.left,val)
  else:
  	return self.searchBST(root.right,val)
return None
  • 迭代：与递归类似，但空间复杂度低（为什么）
1
2
3
4
5
6
7
8
while root:
  if root.val == val:
  	return root
  elif root.val > val:
  	root = root.left
  else:
  	root = root.right
return None

450.删除二叉搜索树中的节点

https://leetcode-cn.com/problems/delete-node-in-a-bst/

题解

  • 删除某个节点时会出现以下情况：

    1. 该节点为叶子节点，直接删除即可

    2. 该节点左子树为空，此时用右子树代替即可；该节点右子树为空，此时用左子树代替即可

    3. 该节点左右子树都不为空时，使用比当前节点小的最大节点predecessor或比当前节点大的最小节点successor替换

解法

  • 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
def delete(root, key, l):
  if not root:
  	return l
  if root.val == key:
  	return delete(root.right, key, root.left)
  elif root.val < key:
    root.right = delete(root.right, key, l)
    return root
  else:
    root.left = delete(root.left, key, l)
    return root

return delete(root, key, None)
  • 迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def successor(self, root):
  """
  One step right and then always left
  """
  root = root.right
  while root.left:
  	root = root.left
  return root.val

def predecessor(self, root):
  """
  One step left and then always right
  """
  root = root.left
  while root.right:
  	root = root.right
  return root.val

def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
  if not root:
  	return None

  # delete from the right subtree
  if key > root.val:
  	root.right = self.deleteNode(root.right, key)
  # delete from the left subtree
  elif key < root.val:
  	root.left = self.deleteNode(root.left, key)
  # delete the current node
  else:
    # the node is a leaf
    if not (root.left or root.right):
    	root = None
    # the node is not a leaf and has a right child
    elif root.right:
      root.val = self.successor(root)
      root.right = self.deleteNode(root.right, root.val)
    # the node is not a leaf, has no right child, and has a left child    
    else:
      root.val = self.predecessor(root)
      root.left = self.deleteNode(root.left, root.val)

  return root

110.平衡二叉树

https://leetcode-cn.com/problems/balanced-binary-tree/

题解

  • 一棵高度平衡二叉树定义为：

    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

  • 每一棵子树也是一个子问题，考虑使用递归

解法

  • 自顶而下（暴力）：构造一个获取当前节点最大深度的方法 depth(root) ，通过比较此子树的左右子树的最大高度差abs(depth(root.left) - depth(root.right))，来判断此子树是否是二叉平衡树。若树的所有子树都平衡时，此树才平衡。
1
2
3
4
5
6
7
def isBalanced(self, root: TreeNode) -> bool:
  if not root: return True
  return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

def depth(self, root):
  if not root: return 0
  return max(self.depth(root.left), self.depth(root.right)) + 1
  • 自底而上（更优）：对二叉树做先序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。
1
2
3
4
5
6
7
8
9
10
def isBalanced(self, root: TreeNode) -> bool:
	return self.recur(root) != -1

def recur(self, root):
  if not root: return 0
  left = self.recur(root.left)
  if left == -1: return -1
  right = self.recur(root.right)
  if right == -1: return -1
  return max(left, right) + 1 if abs(left - right) < 2 else -1

[参考方法][https://leetcode-cn.com/problems/balanced-binary-tree/solution/balanced-binary-tree-di-gui-fang-fa-by-jin40789108/]

  • DFS递归
1
2
3
if not root: return first or 0
l, r = map(lambda x: self.isBalanced(x, False), [root.left, root.right])
return max(l,r)+1 if min(l,r)>-1 and abs(l-r)<=1 else (-1, False)[first]

222.完全二叉树

https://leetcode-cn.com/problems/count-complete-tree-nodes/

题解

  • 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大 值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第$h$层，则该层包含 $1 \sim 2^h$ 个 节点。
  • 已知这是一棵完全二叉树，那么除了最后一层，其他层都是满的，且最后一层的节点全部靠向左边。

解法

  • 递归：没有利用完全二叉树的特性
1
return 1 + self.countNodes(root.right) + self.countNodes(root.left) if root else 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def compute_depth(self, node: TreeNode) -> int:
  """
  Return tree depth in O(d) time.
  """
  d = 0
  while node.left:
    node = node.left
    d += 1
  return d

def exists(self, idx: int, d: int, node: TreeNode) -> bool:
  """
  Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
  Return True if last level node idx exists. 
  Binary search with O(d) complexity.
  """
  left, right = 0, 2**d - 1
  for _ in range(d):
    pivot = left + (right - left) // 2
    if idx <= pivot:
      node = node.left
      right = pivot
    else:
      node = node.right
      left = pivot + 1
  return node is not None

def countNodes(self, root: TreeNode) -> int:
  # if the tree is empty
  if not root:
  	return 0

  d = self.compute_depth(root)
  # if the tree contains 1 node
  if d == 0:
  	return 1

  # Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
  # Perform binary search to check how many nodes exist.
  left, right = 1, 2**d - 1
  while left <= right:
    pivot = left + (right - left) // 2
    if self.exists(pivot, d, root):
    	left = pivot + 1
    else:
    	right = pivot - 1

  # The tree contains 2**d - 1 nodes on the first (d - 1) levels
  # and left nodes on the last level.
  return (2**d - 1) + left

814.二叉树的剪枝

https://leetcode-cn.com/problems/binary-tree-pruning/

题解

  • 可删除本身值为0且没有左右子树的节点

解法

  • 递归：判断是否包含1
1
2
3
4
5
6
7
8
9
def containsOne(node):
  if not node: return False
  a1 = containsOne(node.left)
  a2 = containsOne(node.right)
  if not a1: node.left = None
  if not a2: node.right = None
  return node.val == 1 or a1 or a2

return root if containsOne(root) else None

Note：二叉树部分果然还是比较麻烦的一部分，事后需要多记模版以及多思考